package com.wzw.basics.sort;

import java.util.Arrays;

/**
 * 冒泡排序：从下表为零的元素，依次往后与后面一个元素比较。如果后一个元素小于当前元素就交换位置
 *
 * @author Wangzhiwen
 */
public class BubbleSort {

    /**
     * 10,3,123,43,56,12,9 length=7 [0,6]
     *
     * i=0 0<=j<6 max=123
     * j=0 [3] [10] 123 45 56 12 9 -> 3 10 123 45 56 12 9
     * j=1 3 [10] [123] 45 56 12 9 -> 3 10 123 45 56 12 9
     * j=2 3 10 [123] [45] 56 12 9 -> 3 10 45 123 56 12 9
     * j=3 3 10 45 [123] [56] 12 9 -> 3 10 45 56 123 12 9
     * j=4 3 10 45 56 [123] [12] 9 -> 3 10 45 56 12 123 9
     * j=5 3 10 45 56 12 [123] [9] -> 3 10 45 56 12 9 123
     *
     * 3 10 45 56 12 9 123
     * i=1 0<=j<5 max=56
     * j=0 [3] [10] 45 56 12 9 123 -> 3 10 45 56 12 9 123
     * j=1 3 [10] [45] 56 12 9 123 -> 3 10 45 56 12 9 123
     * j=2 3 10 [45] [56] 12 9 123 -> 3 10 45 56 12 9 123
     * j=3 3 10 45 [56] [12] 9 123 -> 3 10 45 12 56 9 123
     * j=4 3 10 45 12 [56] [9] 123 -> 3 10 45 12 9 56 123
     *
     */
    public static void execute(int[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }
        // 1.每一次遍历后数组中最大的一个元素会被放到最后面
        for (int i = 0; i < arrays.length; i++) {
            /*
             * 2.比较当前元素arrays[j]与下一个元素arrays[j+1]的大小关系
             *   j循环内最大值：arrays.length - 1 - i
             *   -1的原因：j=arrays.length时，j+1会越界
             *   -i的原因：外层循环每经过一次，数组内的最大值就会被放到最尾部后一次循环就无需和最后一个元素进行比较
             */
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                // 3.交换位置
                if (arrays[j + 1] < arrays[j]) {
                    int temp = arrays[j + 1];
                    arrays[j + 1] = arrays[j];
                    arrays[j] = temp;
                }
            }
        }
        System.out.println("bubble sort " + Arrays.toString(arrays));
    }

}
